package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

import java.util.Stack;

/**
 * 0530.二叉搜索树的最小绝对差
 * 给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
 *
 * 题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。
 * 注意是二叉搜索树，二叉搜索树可是有序的。
 * 遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。
 * 那么二叉搜索树采用中序遍历，其实就是一个有序数组。
 *
 * @author Liyc
 * @date 2024/1/12 11:13
 **/

public class Solution19 {
    private TreeNode pre;
    private int resutl = Integer.MAX_VALUE;
    /**
     * 递归法
     * @param root
     * @return
     */
    public int getMinimumDifference1(TreeNode root) {
        if (root == null) return 0;
        travelbal(root);
        return resutl;
    }
    public void travelbal(TreeNode root) {
        if (root == null) return;

        travelbal(root.left);
        if (pre != null) {
            resutl = Math.min(resutl, root.val - pre.val);
        }
        pre = root;
        travelbal(root.right);
    }

    /**
     * 迭代法
     * @param root
     * @return
     */
    private Stack<TreeNode> stack;
    public int getMinimumDifference2(TreeNode root) {
        if (root == null) return 0;
        stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (pre != null) {
                    resutl = Math.min(resutl, cur.val - pre.val);
                }
                pre = cur;
                cur = cur.right;

            }
        }
        return resutl;
    }
}
